/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: list_sort.c 43 2009-11-13 23:27:38Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>

#include "list.h"
#include "list_sort.h"
#include "function_prototypes.h"

void
bubble_sort (List *list, comp_func *comp)
{
  const void *tmp;
  ListNode *cur, *next;
  int swapped = 0; /* This watches for swaps. If we don't swap in a loop, we
		      are done. */

  do
    {
      /* Initialize this run. */
      swapped = 0;
      cur = list->head;
      next = (cur == NULL ? NULL : cur->next);
      
      /* check tail for circular. */
      while (cur != NULL && next != NULL && cur != list->tail)
	{
	  /* If the current item is greater than the next item,
	     switch them. We are bubbling up the list. */
	  if (comp (cur->item, next->item) > 0)
	    {
	      swapped = 1;

	      tmp = cur->item;
	      cur->item = next->item;
	      next->item = tmp;
	    }

	  /* Move up the list. */
	  cur = cur->next;
	  next = (cur == NULL ? NULL : cur->next);
	}
    }
  while (swapped);
}

void
selection_sort (List *list, comp_func *comp)
{
  const void *tmp;
  struct list_node *spos, *min, *cur;

  spos = list->head;

  /* Loop through each of the items in the list. */
  while (spos != NULL && spos != list->tail)
    {
      min = spos;

      /* Loop through the rest of the items. */
      cur = spos;
      while (cur != NULL)
	{
	  /* If the current item is less than the min item, make it the
	     new min. */
	  if (comp (cur->item, min->item) < 0)
	    min = cur;

	  if (cur == list->tail)
	    break;

	  cur = cur->next;
	}

      /* If we found a smaller item, swap it. */
      if (spos != min)
	{
	  tmp = spos->item;
	  spos->item = min->item;
	  min->item = tmp;
	}

      spos = spos->next;
    }
}

void
insertion_sort (List *list, comp_func *comp)
{
  const void *tmp, *value;
  struct list_node *cur, *step;

  /* If we have one item, we are done. */
  if (list_size (list) < 2)
    return;

  /* Start at the second item. */
  cur = list->head->next;
  while (cur != NULL)
    {
      value = cur->item;

      /* Loop through all the items between the head and the current item. 
       Swap all the items that are out of order. */
      step = cur->prev;
      while (step != NULL)
	{
	  /* Sentinel check - this is in order. */
	  if (comp (step->item, value) < 0)
	    break;

	  /* swap the item. */
	  tmp = step->item;
	  step->item = value;
	  step->next->item = tmp;

	  /* Sentinel check - we are at the beginning. */
	  if (step == list->head)
	    break;

	  step = step->prev;
	}

      /* Sentinel check - we are at the end of the list. */
      if (cur == list->tail)
	break;

      cur = cur->next;
    }
}
